
/*
 * pQueue.java
 * Software Engineering Lab 2
 * Oct 10, 2006
 * 
 * By:
 * Dan Grissom - grissodt@email.uc.edu
 * Jon Hoffman - hoffmaj1@email.uc.edu
 * Jon Nafziger - nafzigjw@email.uc.edu
 * Mike Schmidt - schmidm2@email.uc.edu
 * 
 * The Event class is used to store the priority and an informational string of an event.
 */

package pQueue;

// Includes Vectors
import java.util.Vector;

// Defines the Event Class
import Event.Event;

// Defines the pQueue Class
public class pQueue
{
	private Vector<Event> myHeap;	// Defines the heap
	private int frontIndx;			// Defines pointer to front
	private int backIndx;			// Define pointer to back

	/** Constructor */
	public pQueue()
	{
		myHeap = new Vector<Event>(0);
		frontIndx = 0;
		backIndx = 0;		
	};
	
	/** Is Empty function */
	public boolean isEmpty() { return backIndx == 0;}
	
	/** Function to push another Event */
	public void enqueue(Event Input) 
	{
		//Verifies Input is Real Value
		if(Input == null)
			return;
		int tempIndx = backIndx;
		myHeap.add(backIndx++,Input);
		
		//While Loop moves item from bottom to top of pQueue
		while( 
			   ((tempIndx-1)/2 >= 0) &&
		       (myHeap.elementAt(tempIndx).PR < 
		    	myHeap.elementAt((tempIndx-1)/2).PR)
		      )
		{
			swapEvents(tempIndx,(tempIndx-1)/2);
			tempIndx = ((tempIndx-1)/2);
		}
	};
	
	/** Function to pop top priority event */
	public Event dequeue() 
	{
		if(isEmpty())
			return null;
		
		// Creating Events that serve as value holders in Logic
		Event topValue;	
		//Event tempEvent = new Event();
				
		// Remove top value, make bottom value top of the heap
		topValue = myHeap.elementAt(frontIndx);
		myHeap.setElementAt(myHeap.elementAt(--backIndx), frontIndx);
		
		
		int tempIndx = 0;
		while((2*(tempIndx+1) <= backIndx))	{
			if(	myHeap.elementAt(tempIndx).PR >
				myHeap.elementAt(2*(tempIndx+1)-1).PR)
			{
				if (myHeap.elementAt(2*(tempIndx+1)-1).PR <
					myHeap.elementAt(2*(tempIndx+1)).PR)
				{				
					swapEvents(2*(tempIndx+1)-1, tempIndx);
					tempIndx = 2*(tempIndx+1)-1;
				}
				else
				{
					swapEvents(2*(tempIndx+1), tempIndx);
					tempIndx = 2*(tempIndx+1);
					}
				}
			else 
				if( 2*(tempIndx+1) < backIndx)
				{		
					if( myHeap.elementAt(tempIndx).PR >
						myHeap.elementAt(2*(tempIndx+1)).PR)
					{
						swapEvents(2*(tempIndx+1), tempIndx);
						tempIndx = 2*(tempIndx+1);											
					}
					else break;
				}
				else break;				
		}
		return (Event)(topValue);
	}

	/** Function to swap two elements in the heap */
	public void swapEvents(int Index1, int Index2) 
	{
		Event swapEvent = myHeap.elementAt(Index1);
		myHeap.setElementAt((myHeap.elementAt(Index2)), Index1);
		myHeap.setElementAt((swapEvent),Index2);
	}
}
